package org.usmile.algorithms.learn.graph.dfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class GraphDFS {
    /**
     * 深度优先遍历 迭代
     */
    public List<Integer> dfs(Graph graph, int v) {
        if (graph == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[graph.getV()];
        stack.push(v);
        visited[v] = true;
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            result.add(curr);

            for (int w : graph.adj(curr)) {
                if (!visited[w]) {
                    stack.push(w);
                    visited[w] = true;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(8);
        graph.addEdge(4, 2);
        graph.addEdge(5, 2);
        graph.addEdge(6, 2);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(3, 2);

        System.out.println(new GraphDFS().dfs(graph, 0));
    }
}
